package com.clstu.sort;

import java.lang.reflect.Array;
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * 演示冒泡排序过程 --(优化)--->发现有序后提前结束排序
 */
public class BubbleSort {
    public static void main(String[] args) {
        //测试一下是否写对
        //创建数组
//        int[] arr = {1, 2, 3, 4, 5, 6};
//        bubbleSort(arr);
        //测试一下速度
        //1.创建一个80000个数据的随机数组
        int[] arr = new int[8];
        //初始化随机数据
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int)(Math.random()*80000);//范围[0,80000)
        }
//        System.out.println("排序前数组:");
//        System.out.println(Arrays.toString(arr));
        long start = System.currentTimeMillis();
        bubbleSort(arr);
        long end = System.currentTimeMillis();
        System.out.println("冒泡排序80000条数据耗时:"+(end-start)+"ms");//8712ms
        //测试一下情况好的情况下
        long start1 = System.currentTimeMillis();
        bubbleSort(arr);
        long end1 = System.currentTimeMillis();
        System.out.println("冒泡排序80000(有序的)条数据耗时:"+(end1-start1)+"ms");//0ms(优化还是很可以的)
//        System.out.println("排序后数组:");
//        System.out.println(Arrays.toString(arr));
    }

    //编写一个方法实现冒泡排序
    public static void bubbleSort(int[] arr){
        //思路分析;
        //冒泡排序过程: 从前向后遍历,比较自己和自己的后一个数据,
        //            如果比后一个数据大,则交换,遍历完第一次就确定了最大的数并放在了数组的最后
        //                                  遍历完第i次就确定了第i大数并放在了数组的倒数i位置
        //   如果遍历过程种一次都没有发生交换,则证明数组已经有序,提前退出排序
        int tmp = 0;//临时变量,用于交换
        boolean finished = true;//用于判断是否已经有序
        for (int i = 0; i < arr.length-1; i++) {
            finished = true;//假设有序的
            for (int j = 0; j < arr.length-i-1; j++) {
                if(arr[j]>arr[j+1]){
                    finished = false;
                    tmp = arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=tmp;
                }
            }
//            //查看一下每次排序后的情况
            System.out.println("第"+(i+1)+"次排序后:"+Arrays.toString(arr));
            //如果已经有序,提前结束
            if(finished) {
                break;
            }
        }
    }
}
